#include <stdio.h>

//打印数组函数
void print_array(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

//插入排序实现
void insertion_sort(int unsorted_array[], int num_elements)
{
    int i, j, key;
    for (i = 1; i < num_elements; i++)
    {
        key = unsorted_array[i];
        j = i - 1;

        while (j >= 0 && unsorted_array[j] > key)
        {
            unsorted_array[j + 1] = unsorted_array[j];
            j = j - 1;
        }
        unsorted_array[j + 1] = key;

        //每次插入后打印数组
        print_array(unsorted_array, num_elements);
    }
}

int partition(int L[], int low, int high, int total_num_elements)
{
    int pivot = L[low];
    int i = low + 1;
    int j = high;

    while (1)
    {
        while (i <= j && L[i] <= pivot) i++;
        while (i <= j && L[j] >= pivot) j--;
        if (i >= j) break;

        int temp = L[i];
        L[i] = L[j];
        L[j] = temp;
    }

    L[low] = L[j];
    L[j] = pivot;

    print_array(L, total_num_elements);

    return j;
}

//快速排序递归实现
void QSort(int L[], int low, int high, int total_num_elements)
{
    if (low < high)
    {
        int pivot_pos = partition(L, low, high, total_num_elements);
        QSort(L, low, pivot_pos - 1, total_num_elements);
        QSort(L, pivot_pos + 1, high,total_num_elements);
    }
}

//堆排序的辅助函数-调整堆
void heapify(int arr[], int n, int i, int num_elements)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i)
    {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;
        heapify(arr, n, largest, num_elements);
    }
}

//堆排序实现
void heap_sort(int unsorted_array[], int num_elements)
{
    //构建最大堆
    for (int i = num_elements / 2 - 1; i >= 0; i--)
        heapify(unsorted_array, num_elements, i, num_elements);

    //一个个从堆顶取出元素
    for (int i = num_elements - 1; i > 0; i--)
    {
        //将当前根节点移动到数组末尾
        int temp = unsorted_array[0];
        unsorted_array[0] = unsorted_array[i];
        unsorted_array[i] = temp;

        //打印交换后的数组
        print_array(unsorted_array, num_elements);

        //重新调整堆
        heapify(unsorted_array, i, 0, num_elements);
    }
}

int main()
{
    //测试插入排序
    printf("Insertion Sort Test:\n");
    int arr1[] = {4, 3, 2, 1};
    insertion_sort(arr1, 4);
    printf("\n");

    //测试快速排序
    printf("Quick Sort Test:\n");
    int arr2[] = {3, 1, 2, 5, 4};
    QSort(arr2, 0, 4, 5);
    printf("\n");

    //测试堆排序
    printf("Heap Sort Test:\n");
    int arr3[] = {70, 60, 12, 40, 30, 8, 10};
    heap_sort(arr3, 7);
    printf("\n");

    return 0;
}